%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{A weighted connected graph $G = (V,E)$ with weight function
  $w$. All the edge weights of $G$ are distinct.}
%%
%% output
\KwOut{A minimum spanning tree $T$ of $G$.}
\BlankLine
%%
%% algorithm body
$n \assign |V|$\nllabel{alg:Boruvka:get_graph_order}\;
$T \assign \overline{K}_n$\nllabel{alg:Boruvka:spanning_forest}\;
\While{$|E(T)| < n - 1$\nllabel{alg:Boruvka:while_loop_start}}{
  \For{\rm each component $T'$ of $T$\nllabel{alg:Boruvka:for_loop}}{
    $e' \assign$ edge of minimum weight that leaves $T'$\;
    $E(T) \assign E(T) \cup e'$\nllabel{alg:Boruvka:while_loop_end}\;
  }
}
\Return $T$\;
